package gold.digger;

import gold.utils.InputUtil;
import jdk.internal.util.xml.impl.Input;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC962 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int maxWidthRamp(int[] nums) {
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < nums.length; i++) {
                if (stack.isEmpty() || nums[stack.peek()] > nums[i]) stack.push(i);
            }

            int res = 0;
            for (int i = nums.length - 1; i >= 0; i--) {
                while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                    res = Math.max(res, i - stack.peek());
                    stack.pop();
                }
            }

            return res;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[9,8,1,0,1,9,4,0,4,1]");
        System.out.println(solution.maxWidthRamp(arr));
    }

    public static void main(String[] args) throws Exception {
        LC962 an = new LC962();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
